

from Crypto.Util.number import *
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)

p = getPrime(512)
q = getPrime(512)
# print(f'p={p}')
n = p*p*q
c = pow(m, n, n)
d = inverse(n, (p-1)*(q-1))
d1=pow(d,(p-1)//4,p)
# print(f'n = {n}')
# print(f'd = {d}')
# print(f'd1 = {d1}')
# print(f'c = {c}')
# print((p-1)%4)

p = 8857370974292745429928374585798646441077973581458104851995519551682306554254688182936794330573614282041736133510757990800085574535853597183438282574906411
n = 885524869103425243306875590062363437620270822856901367106890847410057049903887459177969502309660078907334946290985057069937434705423581050488161737322348917850522989720553388371088170348052275161372549792971952290951742341343761713067899077840877083543102912925296255717906814509314542407368552578644480584206466999819306778834132447781639618242043740349693244547235802889434496278026073623538349462667374901109512189846242335451792525811106436946605152837076777
d = 65301133914480152554946356344151704212917189776056142708305839114451870081351760776487126909654440750699034473930487562542796021167248190717245303306791349550751476834937933437758463563452246849670795463476031416508933270037859670266567084484778746578735885354824325843957331626052308855649345808808690946553
d1 = 5320862233495186490355826428588594521629569971760968006318950464936773939361609328772776300425356450977656144395280670277012212285564946942522289812033504
c = 75118625218770856611440286454872979820962709973505759026909875453644109494726918119192407194027165526906934062491627394928076268302231659746003148367376011244506963506233227140133141193822211772272815002674478998218703474833324059501790038065117144402328275399709827230895871547233068586700987709940665561511538076266907427364015811275556549187756650583181883722362781863027299709022433061469063117830503536985750985989088840561245970199370484885545215265279798
import libnum
tmp=pow(d1,4,p)
print(libnum.gcd(tmp,n))
tmp1=pow(d,2,p)
print(tmp1)
print(tmp*tmp1%p)
